﻿#include "unit_test.h"
#include <stack>
#include <deque>

namespace code_01_05
{
    /**
     * @brief 从from中把大于value的值全部移到to中
     *
     * @param from 源栈，初始时栈底 -> 栈顶元素呈升序排列
     * @param to 目标栈
     * @param value 要比较的值
     */
    void MoveElementLargerThan(std::stack<int>& from, std::stack<int>& to, int value)
    {
        while (!from.empty() && from.top() > value)
        {
            to.push(from.top());
            from.pop();
        }
    }

    TEST(MoveElementLargerThan)
    {
        std::stack<int> from{ {1, 3, 5} };
        std::stack<int> to{ {6} };              // 本来就有数据
        MoveElementLargerThan(from, to, 2);     // 移动5和3
        std::stack<int> expected{ {6, 5, 3} };
        ASSERT_EQ(true, to == expected);
    }

    void SortStack(std::stack<int>& s)
    {
        if (s.size() <= 1)
        {
            return;
        }

        // 从s中取出元素，插入tmp中，保持有序即可
        // 如果是栈底 -> 栈顶升序排列，那么最后直接交换s和tmp
        // 如果是栈底 -> 栈顶降序排列，那么将tmp中的元素全部压入s中
        // 下面按栈底 -> 栈顶升序排列的方式进行处理
        std::stack<int> tmp;
        while (!s.empty())
        {
            // 拿出一个值
            int top = s.top();
            s.pop();

            // 如果要追求代码短小，可以从两个方面优化：
            // 1、去除if分支，因为MoveElementLargerThan可以处理这种情况
            // 2、tmp.push(top)之后不转移s中刚才插进去的数据，而是留给外部循环处理
            // 最终版本见SortStackShort

            if (tmp.empty() || top >= tmp.top())
            {
                tmp.push(top);  // 升序直接插入
            }
            else
            {
                const auto size = s.size(); // 做标记
                // 把大于top的全部移回到s中
                MoveElementLargerThan(tmp, s, top);
                // 将top插进去
                tmp.push(top);
                // 把原来的数据再放回来，这样tmp依然维持升序状态
                while (s.size() > size)
                {
                    tmp.push(s.top());
                    s.pop();
                }
            }
        }
        s.swap(tmp);
    }

    TEST(SortStack)
    {
        std::stack<int> actual{ {1, 3, 5, 6, 4, 2} };
        std::stack<int> expected{ {1, 2, 3, 4, 5, 6} };
        SortStack(actual);
        ASSERT_EQ(true, actual == expected);
    }

    void SortStackShort(std::stack<int>& s)
    {
        std::stack<int> tmp;
        while (!s.empty())
        {
            int top = s.top();                  // 拿出一个值
            s.pop();
            MoveElementLargerThan(tmp, s, top); // 把大于top的全部移回到s中
            tmp.push(top);                      // 将top插进去
        }
        s.swap(tmp);
    }

    TEST(SortStackShort)
    {
        std::stack<int> actual{ {1, 3, 5, 6, 4, 2} };
        std::stack<int> expected{ {1, 2, 3, 4, 5, 6} };
        SortStackShort(actual);
        ASSERT_EQ(true, actual == expected);
    }
}
